package com.sort;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Random;

/**
 * ClassName: SortMain
 * Description:
 *
 * @author kang.wang03
 *         Date 2016/11/25
 */
public class SortMain {
    public static void main(String args[]) {
        int sort[] = new int[10];
        for (int i = 0; i < 10; i++) {
            sort[i] = new Random().nextInt(1000);
        }
        BigDecimal bigDecimal = new BigDecimal(1.2);
        BigDecimal bigDecimal1 = new BigDecimal(1.22);
        System.out.println(bigDecimal.compareTo(bigDecimal1));
        if (true)return;
        System.out.println(Arrays.toString(sort));
        System.out.println("冒泡排序�?" + Arrays.toString(bubbleSort(sort)));
        System.out.println("选择排序�?" + Arrays.toString(selectSort(sort)));
        System.out.println("堆排序：" + Arrays.toString(heapSort(sort)));
        System.out.println("快排序：" + Arrays.toString(quickSort(sort)));
        System.out.println("插入排序�?" + Arrays.toString(insertSort(sort)));
        System.out.println("折半排序�?" + Arrays.toString(binaryInserSort(sort)));
        System.out.println("shell排序�?" + Arrays.toString(shellSort(sort)));
        System.out.println("s归并排序�?" + Arrays.toString(mergeSort(sort)));
    }


    /**
     * 归并排序
     *
     * @param sort
     * @return
     */
    public static int[] mergeSort(int sort[]) {
        int[] sortTmp = new int[sort.length];
        System.arraycopy(sort, 0, sortTmp, 0, sort.length);
        sort(0, sortTmp.length - 1, sortTmp);
        return sortTmp;
    }

    private static void sort(int left, int right, int[] sortTmp) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(left, mid, sortTmp);
            sort(mid + 1, right, sortTmp);
            merge(sortTmp, left, mid, right);
        }
    }

    private static void merge(int[] sortTmp, int left, int mid, int right) {
        int sort[] = new int[sortTmp.length];
        int tmp = left;
        int third = left;
        int center = mid + 1;
        while (left <= mid && center <= right) {
            if (sortTmp[left] < sortTmp[center]) {
                sort[third++] = sortTmp[left++];
            } else
                sort[third++] = sortTmp[center++];
        }
        while (center <= right)
            sort[third++] = sortTmp[center++];
        while (left <= mid)
            sort[third++] = sortTmp[left++];
        while (tmp <= right) {
            sortTmp[tmp] = sort[tmp++];
        }
    }

    /**
     * @param sort
     * @return
     */
    public static int[] shellSort(int sort[]) {
        int[] sortTmp = new int[sort.length];
        System.arraycopy(sort, 0, sortTmp, 0, sort.length);
        int h = 1;
        while (h <= sortTmp.length / 3)
            h = h * 3 + 1;
        while (h > 0) {
            for (int i = h; i < sortTmp.length; i++) {
                int tmp = sortTmp[i];
                if (sortTmp[i] < sortTmp[i - h]) {
                    int j = i - h;
                    for (; j >= 0 && sortTmp[j] > tmp; j -= h) {
                        sortTmp[j + h] = sortTmp[j];
                    }
                    sortTmp[j + h] = tmp;
                }
            }
            h = (h - 1) / 3;
        }
        return sortTmp;
    }

    /**
     * 折半插入
     *
     * @param sort
     * @return
     */
    public static int[] binaryInserSort(int sort[]) {
        int[] sortTmp = new int[sort.length];
        System.arraycopy(sort, 0, sortTmp, 0, sort.length);
        for (int i = 1; i < sortTmp.length; i++) {
            int low = 0;
            int high = i - 1;
            int tmp = sortTmp[i];
            while (low <= high) {
                int mid = (low + high) / 2;
                if (tmp > sortTmp[mid]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            for (int j = i; j > low; j--) {
                sortTmp[j] = sortTmp[j - 1];
            }
            sortTmp[low] = tmp;
        }
        return sortTmp;
    }

    /**
     * 插入排序
     *
     * @param sort
     * @return
     */
    public static int[] insertSort(int sort[]) {
        int[] sortTmp = new int[sort.length];
        System.arraycopy(sort, 0, sortTmp, 0, sort.length);
        for (int i = 1; i < sortTmp.length; i++) {
            int tmp = sortTmp[i];
            if (sortTmp[i] < sortTmp[i - 1]) {
                int j = i - 1;
                for (; j >= 0 && sortTmp[j] > tmp; j--) {
                    sortTmp[j + 1] = sortTmp[j];
                }
                sortTmp[j + 1] = tmp;
            }

        }
        return sortTmp;
    }


    /**
     * 快排�?
     *
     * @param sort
     * @return
     */
    public static int[] quickSort(int sort[]) {
        int[] sortTmp = new int[sort.length];
        System.arraycopy(sort, 0, sortTmp, 0, sort.length);
        subSort(sortTmp, 0, sort.length - 1);
        return sortTmp;
    }

    public static void subSort(int sort[], int start, int end) {
        if (start < end) {
            int tmp = sort[start];
            int i = start;
            int j = end + 1;
            while (true) {
                while (i < end && tmp > sort[++i]) ;
                while (j > start && tmp < sort[--j]) ;
                if (i < j) {
                    swap(i, j, sort);
                } else
                    break;
            }
            swap(j, start, sort);
            subSort(sort, start, j - 1);
            subSort(sort, j + 1, end);
        }
    }

//    public static void subSort(int sort[], int start, int end) {
//        if (start < end) {
//            int base = sort[start];
//            int i = start;
//            int j = end + 1;
//            while (true) {
//                while (i < end && sort[++i] >= base) ;
//                while (j > start && sort[--j] < base) ;
//                if (i < j) {
//                    swap(i, j, sort);
//                } else
//                    break;
//            }
//            swap(j, start, sort);
//            subSort(sort, start, j - 1);
//            subSort(sort, j + 1, end);
//        }
//    }

    public static int[] heapSort(int[] sort) {
        int[] sortTmp = new int[sort.length];
        System.arraycopy(sort, 0, sortTmp, 0, sort.length);
        for (int i = 0; i < sortTmp.length - 1; i++) {
            buildHeap(sortTmp, sortTmp.length - 1 - i);
            swap(0, sortTmp.length - 1 - i, sortTmp);
        }
        return sortTmp;
    }

    private static int[] buildHeap(int[] sort, int lastIndex) {
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            int k = i;
            while ((k * 2 + 1) <= lastIndex) {
                int biggerIndex = k * 2 + 1;
                if (biggerIndex < lastIndex) {
                    if (sort[biggerIndex] < sort[biggerIndex + 1]) {
                        biggerIndex++;
                    }
                }
                if (sort[k] < sort[biggerIndex]) {
                    swap(k, biggerIndex, sort);
                    k = biggerIndex;
                } else {
                    break;
                }
            }
        }
        return sort;
    }

    /**
     * 堆排�?
     *
     * @param sort
     * @return
     */
//    public static int[] heapSort(int[] sort) {
//        int[] sortTmp = new int[sort.length];
//        System.arraycopy(sort, 0, sortTmp, 0, sort.length);
//        for (int i = 0; i < sortTmp.length - 1; i++) {
//            buildHeap(sortTmp, sortTmp.length - i - 1);
//            //交换堆定和最后一个元�?
//            swap(0, sortTmp.length - i - 1, sortTmp);
//        }
//        return sortTmp;
//    }
//
//    public static void buildHeap(int[] sortTmp, int lastIndex) {
//        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
//            int k = i;
//            while ((k * 2 + 1) <= lastIndex) {
//                int biggerIndex = k * 2 + 1;
//                if (biggerIndex < lastIndex) {
//                    if (sortTmp[biggerIndex] < sortTmp[biggerIndex + 1]) {
//                        biggerIndex++;
//                    }
//                }
//                if (sortTmp[k] < sortTmp[biggerIndex]) {
//                    swap(k, biggerIndex, sortTmp);
//                    k = biggerIndex;
//                } else
//                    break;
//            }
//        }
//    }

    /**
     * 直接选择排序
     *
     * @param sort
     * @return
     */
    public static int[] selectSort(int[] sort) {
        int[] sortTmp = new int[sort.length];
        System.arraycopy(sort, 0, sortTmp, 0, sort.length);
        for (int i = 0; i < sort.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < sort.length; j++) {
                if (sortTmp[j] < sortTmp[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                swap(i, minIndex, sortTmp);
            }
        }
        return sortTmp;
    }

    /**
     * 冒泡排序
     *
     * @param sort
     * @return
     */
    public static int[] bubbleSort(int[] sort) {
        int[] sortTmp = new int[sort.length];
        System.arraycopy(sort, 0, sortTmp, 0, sort.length);

        for (int i = 0; i < sort.length; i++) {
            boolean change = false;
            for (int j = 0; j < sort.length - 1 - i; j++) {
                if (sortTmp[j + 1] < sortTmp[j]) {
                    swap(j + 1, j, sortTmp);
                    change = true;
                }
            }
            if (!change)
                break;
        }
        return sortTmp;
    }

    public static void swap(int i, int k, int[] sort) {
        int tmp = sort[i];
        sort[i] = sort[k];
        sort[k] = tmp;
    }
}
